package com.yangli.leecode.mashib.interview;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/6 15:48
 */
public class ThirtyThree {
    public static void main(String[] args){

        System.out.println(ThirtyThree.mergeStones2(new int[]{1, 3, 4, 5, 1, 1, 1, 5, 5, 5, 7, 5, 1, 2,  5}, 3));
        System.out.println(ThirtyThree.mergeStones(new int[]{1, 3, 4, 5, 1, 1, 1, 5, 5, 5, 7, 5, 1, 2,  5}, 3));


    }


    public static  int mergeStones(int[] stones, int k){
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }
        int [] sum = new int[n+1];
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + stones[i - 1];

        int[][][] dp = new int[n + 1][n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <=n; j++) {
                for (int m =2;m<=k;m++){
                    dp[i][j][m] = Integer.MAX_VALUE;//无效
                }
                dp[i][j][1] = 0;//成本为0
            }
        }
        for (int i = n; i >0; i--) {//从最大开始 ij变化 n-1 ..n    1..n
            for (int j = i + 1; j <=n; j++) {
                for (int m =1;m<=k;m++){
                    for (int p = i;p<j;p+=k-1){
                        dp[i][j][m] = Math.min(dp[i][j][m],dp[i][p][1]+dp[p+1][j][m-1]);
                    }
                    //当i和j不相当等要划分1分,进行计算头痛及

                }
                dp[i][j][1] = dp[i][j][k] + sum[j] - sum[i - 1];
            }
        }

        return dp[1][n][1];

    }

    public static int mergeStones2(int[] stones, int k){
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }
        int [] sum = new int[n];
        sum[0] = stones[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i-1]+stones[i];
        }
        return process(stones,0,n-1,k,1,sum);

    }

    //dp[l][r][p] 表示l。。r位置上，分成p分，需要的成本。k表示几份合并，sum表示数组前缀和，优化计算
    public static int process(int[] stones, int l, int r, int k, int p, int [] sum){
        if(l==r){
            return p==1?0:-1;
        }
        if(p==1){
            int next = process(stones,l,r,k,k,sum);
            if(next!=-1){
                return  next+sum[r]-(l==0?0:sum[l-1]);
            }else {
                return -1;
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int mid = l;mid<r;mid+=k-1){//mid+=k-1优化跳过无效 2:l-r划分p分，可以看成从l..mid为1分，其他的为p-1分
            int next1 =  process(stones,l,mid,k,1,sum);
            int next2 =  process(stones,mid+1,r,k,p-1,sum);
            if(next1!=-1&&next2!=-1){
                ans = Math.min(ans,next1+next2);
            }
        }
        return ans;
    }


}
